// 53.最大子数组合
// https://leetcode.cn/problems/maximum-subarray/

/**

示例 1：

输入：nums = [-2,1,-3,4,-1,2,1,-5,4]
输出：6
解释：连续子数组 [4,-1,2,1] 的和最大，为 6 。
示例 2：

输入：nums = [1]
输出：1
示例 3：

输入：nums = [5,4,-1,7,8]
输出：23

 */

// 思路
// 本题用动态规划
// 动态规划是先得到数量最小时的最优策略，然后渐渐增加元素，每增加一个元素，都更新最优策略，直到所有元素都加进去之后，就得到了所有的最有策略
// 先计算只有一个元素A时，最大和是多少，很显然就是这个元素自己，将其作为只有一个元素的最优策略，比如我们命名为策略mA
// 下一步要新加一个元素B，那最优策略可能为单个B，或者A+B，我们选最有的那个，命名为mAB
// 再下一步要新加一个元素C，这时，我们虽然有ABC三个元素，但是最优策略只需考虑两种：1.单个C，2. C+mAB。因为AB的最优策略，我们在上一步已经计算过了
// 依此类推，每新加一个元素，都从两种策略中，选择最优的那一个即可

// 本题要求的，是求其中某一段连续长度的和最大，那仅需要将数组从后往前遍历，依次得到每一个位置的最优策略，然后取出和最大的那个即可

/**
 * 动态规划，这个版本注释比较清晰，容易理解
 * @param {*} nums
 * @returns
 */
var maxSubArrayCommit = function (nums) {
    let logs = []; // 记录每个位置的最优策略
    let max = -Infinity; // 记录和最大值

    for (let i = nums.length - 1; i >= 0; i--) {
        let method = {
            index: i, // 当前序号
            nums: 1, // 连续元素数量，包含自身
            val: nums[i], // 和
        };

        // 和上一个元素的最优策略比较，得到当前元素的最优策略
        if (logs.length > 0) {
            const lastMethod = logs[logs.length - 1];
            if (lastMethod.val + method.val > method.val) {
                method.nums += lastMethod.nums;
                method.val += lastMethod.val;
            }
        }

        logs.push(method);
        max = Math.max(max, method.val);
    }

    console.log(`${JSON.stringify(nums)} max sum = ${max}`);
    return max;
};

// maxSubArrayCommit([-2, 1, -3, 4, -1, 2, 1, -5, 4]);
// maxSubArrayCommit([1]);
// maxSubArrayCommit([5, 4, -1, 7, 8]);

/**
 * @param {number[]} nums
 * @return {number}
 */
var maxSubArray = function (nums) {
    let logs = [nums[nums.length - 1]];
    let max = nums[nums.length - 1];

    for (let i = nums.length - 2; i >= 0; i--) {
        let method = nums[i];

        const lastMethod = logs[logs.length - 1];
        method = Math.max(method, method + lastMethod);

        logs.push(method);
        max = Math.max(max, method);
    }

    // console.log(`${JSON.stringify(nums)} max sum = ${max}`);
    return max;
};

maxSubArray([-2, 1, -3, 4, -1, 2, 1, -5, 4]);
maxSubArray([1]);
maxSubArray([5, 4, -1, 7, 8]);
